20240630 494 - Medum - Array

494. Target Sum

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # p
        # s-p
        # p-(s-p)=t
        # p=(t+s)/2
        n = len(nums)
        target += sum(nums)
        if target < 0 or target % 2:
            return 0
        target = target//2  # target

        f = [0] * (target+1) 
        f[0] = 1
        for i, x in enumerate(nums):
            for c in range(target, x-1, -1):
                f[c] = f[c] + f[c-x]
        return f[target]